package com.leetcode.周赛.第234场;

/**
 * @author: xiaomi
 * @date: 2021/3/28
 * @description: 5715. 还原排列的最少操作步数
 * https://leetcode-cn.com/contest/weekly-contest-234/problems/minimum-number-of-operations-to-reinitialize-a-permutation/
 */
public class B_5715_还原排列的最少操作步数 {

    static B_5715_还原排列的最少操作步数 action= new B_5715_还原排列的最少操作步数();

    public static void main(String[] args) {
        int n=12;
        int res = action.reinitializePermutation(n);
        System.out.println("res = " + res);
    }

    /**
     * 只能根据我发现的规律来解题了。
     * 不然暂时没有思路,假设只研究 1 位置的变动
     *
     * @param n
     * @return
     */
    public int reinitializePermutation(int n) {
        if (n == 2) {
            return 1;
        }
        if (n == 4) {
            return 2;
        }
        int nextBegin = n >> 1;
        int count = 1;
        int nextOne = 2;
        int endIndex = n - 2;
        while (true) {
            if (nextOne == endIndex){
                return count << 1;
            }
            if (nextOne==1){
                return count;
            }
            if (nextOne < nextBegin) {
                nextOne = (nextOne) << 1;
            }else {
                int diff= nextOne-nextBegin;
                nextOne = (diff << 1) + 1;
            }
            count++;
        }

    }
}
